package DynamicProgramming;
/**
 * 描述
 * 给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。
 *
 * 数据范围: 1 ≤n,m≤500，矩阵中任意值都满足
 * 要求：时间复杂度 O(nm)O(nm)
 *
 * 例如：当输入[[1,3,5,9],[8,1,3,4],[5,0,6,1],[8,8,4,0]]时，对应的返回值为12，
 *
 *
 * */
class BM68 {
    /**
     *
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        // write code here
        //每次只能向右或者向下走,所以当前点的值取决于上边或者左边中最小的值+当前值
        //dp[i][j]  表示到当前位置的最小路径和
        int[][] dp = new int[row][col];
        //初始化第一行第一列,因为这是单向的只能累加,初始化为该路径的累加和
        int sum = 0;
        for(int i=0;i<col;i++){
            sum += matrix[0][i];
            dp[0][i] = sum;
        }
        sum = 0;
        for(int i=0;i<row;i++){
            sum += matrix[i][0];
            dp[i][0] = sum;
        }
        for(int i=1;i<row;i++){
            for(int j=1;j<col;j++){
                //每次只能向右或者向下走,所以当前点的值取决于上边或者左边中最小的值+当前值
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + matrix[i][j];
            }
        }
        return dp[row-1][col-1];

    }
}
